package queue_stack.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 杨辉三角
 * https://leetcode-cn.com/problems/pascals-triangle/
 */
public class Num118 {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> first = new ArrayList<>();
        first.add(1);
        ret.add(first);
        if (numRows == 1) {
            return ret;
        }
        List<Integer> sec = new ArrayList<>();
        sec.add(1);
        sec.add(1);
        ret.add(sec);
        if (numRows == 2) {
            return ret;
        }
        // numRows >= 3
        for (int i = 3; i <= numRows; i++) {
            // 先取得前一行的数据
            List<Integer> prevList = ret.get(i - 1 - 1);
            List<Integer> curList = new ArrayList<>();
            curList.add(1);
            for (int j = 2; j < i; j++) {
                // [i,j] = [i - 1,j - 1] + [i - 1,j]
                int jValue = prevList.get(j - 1 - 1) + prevList.get(j - 1);
                curList.add(jValue);
            }
            curList.add(1);
            ret.add(curList);
        }
        return ret;
    }
}
